 // 用来保存链表子元素
 class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}

// 链表
class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
    // 添加元素
    append(element) {
        // 创建新的链表元素
        let node = new Node(element),
            // 指针
            current;
        // 如果没有链表头，该元素为表头
        if (this.head == null) {
            this.head = node;
        } else {
            // 有表头，遍历链表，把创建的链表元素添加到最后一项的next后面
            current = this.head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = node;
        }
        // 链表长度加1
        this.length++;
    }
    // 在指定位置移除元素
    removeAt(position) {
        if (position > -1 && position < this.length) {
            let current = this.head,
                index = 0,
                prev;

            if (position === 0) {

                header = current.next;

            } else {
                while (index++ < position) {
                    prev = current;
                    current = current.next;
                }
                prev.next = current.next;
            }
            length--;
            return current.element;
        } else {
            return null;
        }
    }
    // 在任意位置插入一个元素
    insert(position, element) {
        // 注意这里可能会添加到最后，所以<=链表长度
        if (position > -1 && position <= this.length) {
            let node = new Node(element),
                current = this.head,
                index = 0,
                previous;

            if (position === 0) {

                this.head = node;
                node.next = current;

            } else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = node;
                node.next = current;
            }
            this.length++;
            return true;
        } else {
            return false;
        }
    }

    // toString方法实现
    toString() {
        let string = '',
            current = this.head;
        while (current != null) {
            string += current.element.toString();
            current = current.next;
        }

        return string;
    }

    // indexOf方法实现
    indexOf(element) {
        let index = 0,
            current=this.head;

        while (current != null) {
            if (element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }

    // 移除指定元素
    remove(element){
        return this.removeAt(this.indexOf(element));
    }
    // 是否为空
    isEmpty(){
        return this.length === 0;
    }
    // 返回链表长度
    size(){
        return this.length;
    }
    // 获取链表头
    getHead(){
        return this.head;
    }
}